n=700;
m=5000;
k=3000;
D=[55,82,58,49,9,22,21,73,36,83,34,79,84,79,76,84,7,26,91,60,27,48,33,82,31,83,88,67,65,90,70,15,18,30,44,4,86,80,27,1,68,97,74,28,56,50,78,49,36,6,61,77,18,58,16,7,53,60,21,90,95,7,69,57,62,73,90,57,7,77,79,39,92,98,11,20,8,90,82,91,82,55,92,39,94,90,7,14,7,99,86,19,30,15,92,12,53,86,53,69,45,5,2,83,9,60,40,2,100,77,5,28,75,8,55,72,69,21,63,31,10,1,43,38,72,5,20,2,61,1,24,83,91,90,70,42,70,29,1,19,17,70,17,7,73,22,58,94,45,89,94,91,41,1,28,72,71,25,80,19,1,26,4,35,49,38,41,87,3,100,83,97,86,53,5,33,99,31,97,72,1,92,18,13,92,67,89,59,18,7,20,5,41,6,35,77,71,40,22,62,12,37,44,38,48,7,53,72,22,45,81,15,74,1,47,69,75,91,39,85,26,48,52,50,57,28,39,29,25,68,54,59,81,53,94,69,41,43,45,98,44,42,25,97,66,29,27,39,39,66,29,33,25,39,5,77,26,12,47,96,100,91,59,3,7,7,12,22,95,25,78,34,43,74,97,28,19,74,40,64,31,91,59,60,89,68,49,98,67,63,40,85,95,19,55,92,93,7,11,62,69,57,11,52,30,99,86,43,52,86,73,91,75,26,66,88,85,20,66,45,68,40,56,92,6,62,16,12,75,89,85,60,27,4,28,73,9,47,26,15,97,8,90,100,75,71,41,27,90,61,60,55,50,27,85,46,70,36,34,39,10,50,8,80,86,33,9,16,25,93,59,30,71,53,32,36,32,95,56,13,75,41,97,91,79,32,26,98,37,3,3,83,9,56,75,22,8,76,63,17,13,30,45,78,81,79,49,97,73,49,55,64,31,76,63,45,65,11,23,32,1,21,53,42,24,53,59,47,64,77,69,88,61,20,2,38,23,44,19,13,34,73,35,26,41,40,17,86,27,41,61,20,66,85,95,23,47,5,54,77,31,53,75,66,85,5,4,91,29,83,94,43,91,88,26,46,38,75,63,76,54,61,43,14,26,75,42,42,10,2,86,38,66,54,54,34,94,88,94,95,16,25,80,48,21,64,94,16,64,36,14,73,77,83,9,59,7,40,36,8,46,10,54,34,22,70,48,16,2,78,44,44,15,12,31,6,11,59,59,68,42,95,53,17,47,36,71,98,72,19,7,28,58,68,27,75,26,13,51,16,64,1,6,65,98,42,66,75,93,76,35,3,20,96,60,74,59,30,82,99,13,56,50,2,66,16,79,99,54,29,82,47,9,43,45,31,85,50,57,86,79,4,96,52,10,24,95,90,38,39,9,11,34,43,62,74,99,71,4,89,31,48,70,36,54,23,84,92,41,85,49,80,98,82,53,75,33,14,95,12,98,91,28,33,20,84,73,56,20,24,9,61,20,17,6,7,72,78,59,42,93,77,36,91,57,29,30,52,64,78,23,68,22,64,91,41,82,36,85,69,25,39,55,40,93,13,70,64,82,38,19,64,5,20,84,65,76,76,44];
T=[21317,724,875,10274,1,19038,1430,599,16717,53687,5563,11927,11162,18000,2399,13625,4449,3099,2935,309,33798,6983,2117,12256,21390,20002,35797,9788,4152,40133,881,19216,9599,10987,5445,24293,33826,14447,28531,19737,538,106,1377,176,26098,5765,373,1106,287,8088,23683,33661,2751,9403,562,225,280,2019,8773,322,5747,28796,36,20923,11994,4394,13059,643,6658,4068,19079,22627,42497,9406,2145,18464,27563,2167,12988,4514,613,462,9961,20866,17796,12319,5196,340,24221,1603,51,1133,28745,34700,1589,475,4144,12111,4185,5149,153,18167,3148,5550,2754,2614,5648,7865,2961,1962,9400,372,9642,8085,394,8426,155,97,5862,6691,6389,28568,2278,688,404,4547,1702,6096,6869,9847,31960,24447,20775,6290,18900,17045,18594,18369,43133,3949,1557,1841,31596,20388,9226,4289,2644,34297,1556,2735,7177,3817,35722,29161,25368,8716,19421,8117,531,10475,13597,18986,1681,2115,17285,4070,4168,28304,2453,1901,392,5046,783,16197,13791,37618,4097,11638,6934,272,3730,1795,52162,8134,23760,3628,74,497,23636,15395,7062,25037,2429,8955,1290,3404,3733,6260,4495,25497,2392,5797,2664,4700,987,24,33020,143,2739,251,33990,20238,11878,271,3434,14958,7230,11604,2015,2961,609,7026,8041,15145,991,1829,1731,1036,2126,7129,5253,20431,18260,178,7072,7008,9152,918,2938,8988,212,15967,1,4578,23182,3057,3169,275,34647,10780,1891,37928,10446,23319,161,3514,18535,15652,10092,371,2881,6,6167,9433,27657,519,19958,1007,1540,10167,4342,34020,21096,14668,15925,4447,219,14891,18355,2600,9288,2862,867,80,1355,50028,26556,34875,1513,7632,2479,20384,7141,19901,12117,16062,45906,5634,9003,2980,4909,1673,415,29636,2629,1004,1833,7703,3226,2736,550,300,508,7209,29982,26,15156,2496,8880,255,11527,443,912,28812,20142,52574,87,30936,14045,16056,2625,245,41234,69,1393,3829,170,3783,9069,29378,22296,201,6730,416,30290,895,21373,11715,179,5156,3612,24099,6914,183,777,2351,7258,22269,10895,1755,5349,1127,9665,9397,10508,27125,56,384,15899,12691,6081,34214,13906,18970,32699,25701,7887,896,24344,646,21460,2779,720,1984,9797,15913,40597,11088,2094,6105,1255,1822,5528,11981,28383,1436,933,2152,5960,30654,46774,1470,1511,2063,1247,3702,380,7562,12811,4560,2024,6031,10546,5199,3753,7062,8049,92,7826,1812,29080,7980,11291,29076,9049,4758,986,20936,39069,878,7909,6341,1031,445,35610,4144,8719,44062,642,35,2242,1087,5636,3911,10607,2706,2146,5976,5136,5802,27676,3777,38,5019,468,6711,357,3816,219,4886,12401,8961,4792,4159,2234,38054,1009,6109,13188,461,11808,38850,58,3934,1316,3133,13749,23952,3777,5432,2216,19058,1,6548,27651,769,21398,4302,46894,13485,284,4956,8184,3270,9167,47385,15173,12252,5329,2941,36017,562,2417,13811,618,266,383,3126,1683,293,1644,4137,16938,3473,4577,694,3019,1934,2929,6741,287,790,1117,697,81,12584,19490,3914,34783,24408,8434,9186,1068,92,5472,11012,4116,11493,5443,693,9162,10492,4049,1252,638,6891,7231,9775,3697,12431,12220,297,3866,3001,18863,7158,7270,16832,3852,11938,134,5740,3135,16567,1134,932,1712,4005,27955,8355,65,823,2419,7600,2377,10648,6602,171,8144,2364,1015,340,6338,889,8589,10450,21302,21862,60,5717,26506,1657,3904,882,11205,31079,3472,12569,6615,1326,14605,1009,900,5934,380,3207,1635,5179,23152,5166,14386,1045,17100,1665,128,247,6343,30470,581,671,13765,824,1962,3183,8451,5570,10370,16431,261,1500,1726,24730,2312,6362,18892,6025,2503,262,3523,8003,21324,193,1885,12932,2516,15773,5523,9760,9173,655,39378,19351,3516,1444,58213,11253,1546,6816,18079,3534,6018,523,18856,6851,53907,12447,1780,8947,3455,29478,936,210,53,430,21570,2418,2248,5529,66408,2984,11462,1093,1969,339,1,165,14845,19565,8460,10060,8839,8899,2316,13043,10997,7939,14939,3573,22218,23688,80,1002,9128,7475,43832,10953,5092,1620,6225,5214,7376,13862,325,9145,3162,5072,148,3642,1200,9263,8028,17069,5993,1380,3846,9195,5624,6839,15013,3477,11766,29734,478,719,3335,2724,179,6438,25,57779,3328,1302,16029,2994,42016,21749,3718,2984,6907,11208,240,5474,260,2422,642,26325,1052,327,1989,675,15066,664,9914,10766,3110,2254,12410,33537,8695,6780,2192,5613,634,259,4686,9543,1392,201,6438,634,20230,10111,2838,32662,1,4568,9002,3645,1427,3767,2684,396,242,6618,8465,25786,17454,20556,5384,17768,5246,22852,23474,11900,876,2659,17361,417,5121,1171,38,693,16745,367,2774,4631,14954,12757,371,2195,3788,9616,25778,1901,3278,13017,7925,24494,6715,1995,24627,10781,19305,14768,4762,1185,1414,249,328,12377,1172,2311,25160,32667,17817,4713,18242,1424,7996,3918,620,1280,30679,1261,2162,3505,8095,25398,2921,5283,5913,13262,3332,19997,43387,284,3404,556,2360,17361,8860,277,316,145,592,10812,23903,6633,1273,17936,1338,662,3661,28574,1154,310,2291,18395,1856,87,5274,15030,9537,6372,1551,2529,34044,1001,15922,14209,1514,5104,533,4292,4331,7592,4656,5659,28933,22326,2095,2188,15325,2912,25366,6738,1077,5761,38495,6337,17094,10369,20863,6018,2394,3688,4938,80,15529,36826,17488,577,1577,26251,584,3062,25189,19868,3044,69,13442,234,20348,10842,10065,18971,8579,11612,2943,2642,15373,82,675,829,1682,2127,8046,103,47103,12726,20246,260,164,5644,4019,30841,13090,4043,38960,405,19954,9508,1,2918,21579,10857,22637,1127,76,6071,877,4983,4,1992,1802,11272,6704,20818,9774,597,1364,20548,1416,2517,5996,10574,40,1057,33243,10425,40013,19263,2514,7264,100,3433,2182,121,7192,2765,5578,1321,17352,18976,2996,28764,2683,9671,1466,2110,1406,1908,2783,841,2587,14671,32336,7406,2580,10254,332,25,1482,1,2874,1840,2251,970,7999,6513,18917,1500,8935,419,9546,150,1944,607,11862,3240,4590,455,12375,21362,6582,14036,20061,15327,1143,3995,754,35851,23076,4798,2065,2096,1674,3899,9364,8769,2761,7128,2149,1642,18776,18735,39,4258,28126,392,19529,4652,5721,3178,22512,9276,23222,7211,23052,32977,15209,1,146,5691,2847,2096,1995,147,18018,266,22173,10882,4853,14180,6666,136,1499,461,409,2132,1776,12218,1855,46,13451,1848,1220,535,2987,21717,20901,5683,1343,11243,10687,3155,32763,39273,7131,8591,3893,6084,6948,661,1468,6055,20380,7108,1736,8505,16069,5710,15760,4479,983,2972,40453,5611,3340,2794,12603,3210,1539,19609,5509,6286,2670,327,1926,2333,52966,2989,31528,17432,12769,18758,867,2790,3234,7021,286,22979,27733,2093,38242,4715,56,11486,12335,1917,618,22519,8487,21228,3879,1281,833,6146,1976,5225,3236,156,18894,13326,9472,33179,28528,934,6088,8570,17,5238,1610,13126,8206,20355,5572,13390,11608,1129,353,1194,876,920,1853,73,20704,7257,805,14161,592,1189,37,4471,20,31089,25938,5028,43827,5162,4543,15079,6305,1532,3998,343,11223,3005,11156,25834,11712,13519,7136,11414,4868,2933,466,3713,624,7380,2528,17637,186,9828,9498,7112,7300,23380,5080,30,1289,4523,2677,1400,4191,499,26715,2624,3502,5553,9496,6435,9809,17556,12796,7989,11646,1568,1754,5076,10945,478,46247,4171,8003,2423,33,13542,12374,3519,5682,28202,407,1725,2673,6558,489,13350,2812,45224,610,995,13434,19532,160,18279,13463,20560,3810,1643,7918,14480,8906,8780,12032,9068,17643,2554,1844,3122,124,2581,419,15983,248,17349,222,658,4254,12154,1031,3246,980,29781,6997,475,24636,372,4935,23662,498,12817,4716,16222,2504,46128,10690,46010,343,6909,6848,4272,3059,19729,1605,7820,2863,8315,7150,10531,20492,13135,3985,33,31885,11202,46135,6107,6033,2083,1414,15720,1839,6587,1537,1,4231,5688,18,13919,5362,5497,13970,8062,2524,13418,35924,43,13268,14763,4751,4165,443,7394,9210,8709,804,130,454,34,812,1143,37699,13735,26,2376,1006,22815,18289,335,1415,14565,7475,29614,16207,13294,8,10538,26616,3582,761,40,33600,2768,18422,12661,8226,20966,58,5945,14999,19725,5,1185,7793,2609,740,547,503,102,3262,5404,8275,2694,14031,1256,13999,21111,2706,716,5391,7633,16125,4624,5966,14012,8967,9212,10750,290,470,3676,684,20744,34710,141,4231,7609,12842,23341,21153,5449,2900,12812,1956,18072,208,28,473,2244,4123,4676,3484,5874,1926,22323,58,20267,7224,5935,14730,651,38708,893,2073,9299,12122,876,7913,518,48084,388,1719,34870,12512,4301,15345,9648,5817,4072,33908,8553,25453,36910,562,3130,13954,20536,3803,18783,1914,13156,793,22505,3198,21799,20558,9290,1455,2465,13812,7972,3361,5562,2473,12483,16323,1,5105,5002,567,3691,14045,11799,8569,5645,1528,16791,9689,11617,6787,6269,5760,3052,3821,3101,583,1108,2158,6898,3210,5371,2583,30260,5522,1293,6472,6112,12449,3986,1,12855,22983,1190,169,9472,14136,19165,13969,18772,267,9703,7124,34091,1,18,267,6135,2476,2135,20603,1464,11534,3241,9275,498,36840,1625,20858,5709,3456,3915,16649,6188,2458,17463,341,285,5545,54180,19946,23629,33808,32310,96,180,4,9266,3814,1766,9,2696,1080,1575,2122,919,4384,1794,4775,7308,398,8395,5270,8094,9417,522,13192,2281,2445,1,9918,13234,1374,10144,828,10,4375,294,27953,1050,1474,17556,2115,875,1391,2761,16214,16749,34861,12121,5008,6487,513,11487,604,3759,2474,14391,910,182,59322,11008,1752,1,2116,4094,47048,9673,1424,3720,24913,6894,6845,8394,1922,25118,16758,25329,15730,10791,325,621,1813,9407,8862,1829,1427,31101,1079,4535,6350,848,4027,4060,667,3018,6157,7015,28279,687,4199,34472,1353,4781,1676,3028,2808,8737,1415,47598,4485,8594,412,57910,2431,9723,4901,23280,3673,821,35183,3616,1964,3061,953,38338,12819,1402,30059,3727,492,1474,10031,18028,18997,9637,132,316,39763,8544,1461,23852,2488,22419,3294,5016,2135,2661,9348,7448,3523,850,27749,30580,2980,41,13102,20481,2153,30863,3689,904,3746,8429,7004,254,6017,5951,1661,9968,17861,3132,63,21329,5342,4202,24923,5832,25890,1639,8009,1874,6568,5014,2569,21287,8747,8508,41808,1405,3441,9661,1988,924,14886,5120,2610,3319,19412,15411,740,18,13313,2980,4925,1196,34398,3337,42027,4867,473,11417,1,700,20965,15182,7330,1155,2905,4341,26820,1993,2529,3169,20151,1213,5907,122,7514,9679,9535,7829,1352,4028,9356,37958,1344,55047,3816,46788,67,2946,3433,12129,12635,1888,14807,6591,19417,3166,536,8529,21,10266,59,454,8113,14742,9,37353,5917,1954,5740,6961,29178,419,3697,7391,109,2205,14519,2861,833,9669,8440,3697,875,4436,1527,4470,1463,3709,5133,35847,999,1978,12189,29556,1103,21137,5412,21290,816,8644,13,12736,4347,23959,24162,5683,2440,4210,331,9639,13687,76,29020,4139,714,1339,2825,11119,6537,35259,1232,1322,5531,27652,4465,8246,161,8552,3828,1267,13697,2014,13999,16401,37834,20055,7595,21535,299,23298,491,6415,32625,8550,27496,2179,5181,193,572,11235,7126,1,138,5311,2242,2028,1,33307,12695,676,11303,236,81,1463,387,17133,32864,6579,1288,2126,11249,16619,3079,3146,684,16271,4664,743,6520,4643,6545,1906,2816,14171,22530,1967,2477,1007,3225,40844,17092,16379,7701,10796,9451,5045,3244,3970,1487,14286,5752,23889,8477,11922,21733,2761,1222,336,338,1059,11663,4104,403,8166,114,30170,29502,5164,12877,6027,117,11927,54000,189,2894,5740,3621,6379,30865,809,3465,10814,13258,2494,1641,4239,6867,20282,585,2915,10781,363,809,5691,227,2038,1244,1007,6633,5000,5637,94,12302,9385,19022,25661,433,444,364,28912,12826,1460,8737,8289,1939,5335,686,588,43591,43364,17449,18591,1651,1495,18694,295,727,21649,30025,2650,24691,63440,17730,1303,10693,15799,5823,4400,42434,12734,696,12488,48040,10228,26539,1989,1,3652,19677,6773,1116,6521,14773,14824,7646,9882,439,29280,5830,27774,74,47,12762,9537,2124,12420,6106,11767,1931,5634,2499,989,5603,6344,3274,526,43991,17294,13362,5232,476,3505,810,1310,14070,379,5057,417,34123,795,1117,532,2921,11335,24460,7372,627,906,344,47669,6123,38428,18072,775,19311,17658,518,5669,20986,16892,7022,1286,1253,17006,30928,7782,10281,1266,7993,19491,2249,1565,11999,1816,18543,5440,20791,3772,12849,10747,963,11243,15670,1,20172,1055,8555,6940,26106,14038,1521,7978,1229,7650,7450,41643,3117,68,34529,1947,788,2174,8179,4285,2476,10582,6309,501,174,4921,1249,865,1437,5860,4053,17280,1056,171,12076,740,1644,3205,2632,6138,13149,674,17942,2470,272,2483,1340,4220,10483,2699,6815,221,9373,837,1115,12400,2719,768,6703,24753,1803,14913,3268,10092,32000,30784,6108,965,36453,3754,1762,5693,558,31832,1902,4421,19959,1306,7784,5857,4259,15677,2461,2665,2205,4388,40907,1279,2821,12507,3225,2496,2555,23583,6494,8169,376,50486,611,9650,2959,328,4510,190,10179,5808,15537,1446,10531,3137,992,596,868,654,311,3341,8733,2593,5180,762,1205,360,31335,4455,17642,3129,34231,4189,10780,11809,395,2990,2166,20275,69,72,2055,284,1951,390,5349,10035,3079,15548,83,3182,95,4313,41430,5195,13647,1298,337,155,29290,2570,6097,7613,4472,15,829,8769,13400,7354,3552,606,642,1006,841,13832,4155,3676,3251,2802,5707,9570,10282,1764,11150,1699,536,31140,1488,9527,2204,534,4363,2123,5852,24153,249,694,2948,3944,11399,2653,364,489,4397,16758,4337,2240,37298,3682,4150,5896,4429,8766,586,830,28563,3675,13194,1092,5142,12709,246,15033,27683,258,6669,1288,5189,259,9937,672,1176,35859,3766,2107,17504,525,15079,15745,12955,17241,32399,4564,10114,5826,38608,512,5792,29976,114,11718,4496,1628,7311,195,23410,3175,1163,985,3146,2158,3051,1484,25194,256,1284,77,413,389,1939,1202,4634,1856,1141,18912,2213,2153,2131,383,2635,7871,5110,3660,964,37061,7,18351,670,8895,14462,22746,47471,539,3484,9822,10362,12286,35291,10789,1840,2266,21632,31931,10417,6724,134,30024,12816,6879,10364,1163,8346,2558,1524,4719,4900,30281,1588,805,39771,20063,7197,1409,27659,3249,7730,2440,7327,5550,30255,3632,3259,1979,5249,27122,43408,18752,3766,3469,1082,4014,40581,490,3421,4098,31476,2,1537,6391,14703,1411,3861,7882,809,7300,3331,4646,16283,3337,1244,263,100,22514,4723,38791,14462,10370,1635,3519,4939,3616,1086,32103,167,342,17642,64,6351,9714,12680,7036,4951,6407,63,7741,50775,4885,9712,7240,1,257,1885,9400,5067,553,20594,4510,28567,4316,1,26959,293,14127,1173,2826,2255,601,938,2355,4491,341,5180,11225,7497,24877,8237,287,6650,3928,10773,33514,6306,32367,2472,389,10235,2882,6112,2899,1,2503,148,13541,253,231,6577,194,13870,2027,8401,79,8828,17561,4469,1397,6516,946,16694,170,116,13086,1344,14,778,8370,18537,5476,27625,1644,181,1228,848,9770,4429,1570,12178,29163,9008,7102,5695,4564,16120,48,2244,39,3517,4,1942,157,301,3298,2304,445,202,1785,9970,9347,1150,120,1571,227,1,53,3229,4131,801,25093,9510,3950,13996,1097,4094,11595,44,13927,10159,908,12875,10095,108,7723,11648,148,9114,8121,1215,1,4546,11112,7840,631,16996,4050,1961,3624,38635,4741,5391,4733,574,389,1167,1933,14658,13748,19998,8562,6929,2731,1767,671,32727,336,4136,5822,3871,8099,19128,38015,51,14417,12405,25864,2876,15579,1717,15792,16362,34897,1,1,1313,11284,15285,138,17719,4517,1814,16406,360,123,7564,12156,3384,496,598,2822,7526,513,1003,19891,21073,10862,21029,3129,1825,27358,9493,7356,5805,6204,1866,8663,9685,2081,20307,17023,12123,560,4477,4627,4438,9790,6310,1811,26970,12769,1054,2112,1000,2232,4446,10001,1,18565,13022,721,13263,171,20682,4303,3689,126,100,14456,5498,16474,28479,693,6486,12176,1380,5229,7258,2178,1885,9633,384,36,17820,4886,29926,1122,18184,739,2463,101,28659,18413,8916,5688,47780,45961,10504,12830,8005,37021,3865,15703,851,5960,4466,1911,40372,6492,2061,18597,32386,7791,190,20475,2592,7197,6726,246,10964,14731,11408,5061,13646,4273,7236,1487,14713,2099,11787,12911,19,43908,20008,9931,5221,12927,9712,37852,42458,1173,1790,22570,12202,19168,5311,360,10085,1,5919,3084,4733,4419,632,1479,2410,533,1741,4545,14802,3352,18395,3403,7514,15228,12715,11333,335,11,7294,1352,1135,708,7273,1040,14511,5127,1459,14995,15724,1725,438,11635,3032,1136,9717,2,5796,8117,2452,3370,15131,4497,10019,222,799,543,3271,3206,4214,2295,33,29960,1841,4470,18769,138,1837,3218,14008,14249,1,1914,14037,198,12811,2871,1280,940,7926,11,6536,12493,2171,5679,11270,12516,2990,5901,22645,22596,27219,36,796,46781,3182,1951,468,310,12066,14434,9086,6381,1546,7403,1803,4886,19705,1568,21761,2559,513,144,1160,138,7953,15419,786,12243,12278,36366,1113,465,1,366,2380,3503,22753,773,4071,17,1358,863,24386,740,1540,20356,363,7673,12562,11989,12842,150,664,411,7905,17432,10952,473,16882,83,18338,9667,3851,34,4296,26531,8748,41,404,2621,1216,5374,641,6348,905,21170,5894,1562,123,1226,8633,10253,37390,9851,1326,8296,456,875,10305,6013,12605,8867,2849,38809,105,303,553,681,4256,1737,700,5657,7044,1455,1040,2691,164,3619,16252,14331,16264,5151,3410,19181,18636,2464,3205,1570,369,2010,6657,16018,2534,473,9418,15002,5583,13167,25732,7295,9468,1700,24639,3722,656,7543,269,36959,5802,390,6677,14364,22268,21713,3001,11230,18159,1317,12287,11370,198,1969,388,16154,468,21536,3238,6409,20009,13529,19275,32707,8204,1585,10342,13993,22131,8182,11126,734,8594,408,40120,55,18132,23724,500,1559,478,2728,6747,28743,9467,17843,15513,716,740,267,1539,11165,515,3014,1071,15848,14584,28229,918,2096,25978,11963,21780,9706,8839,4913,22615,7520,7687,17373,1,909,3,9385,1844,1116,196,1,6,4182,1484,6313,24,3588,1,3874,13697,28340,35103,3323,8149,1137,1522,20586,17841,38341,5858,40916,3021,2280,597,16005,1935,2935,868,5882,1,20196,19671,6985,1688,607,14734,24362,227,784,11429,8077,5651,27515,21,1190,715,5284,13774,175,1,330,304,44732,5805,1920,1044,1345,12762,5274,2839,1820,3308,7552,14547,285,607,1728,6901,4816,48,84,2948,25651,1529,8254,7404,12950,1889,328,23003,16863,228,10547,6281,45,3533,769,1008,2497,619,7570,1072,11372,232,24312,3213,60,2841,2875,5474,145,7116,14276,66,6233,11346,2607,6704,2228,3731,1,9345,5934,13006,4388,10838,1,3254,878,2329,15354,8268,3801,3246,1529,9957,1174,36314,11504,18220,7825,5662,4319,7633,1054,45969,3915,3989,14160,28,5154,8523,396,4267,8074,4636,865,5701,16639,1750,599,7942,100,4727,15373,416,3692,8088,756,2295,17090,9468,13039,6441,24080,293,143,12670,23093,3063,14492,5401,7419,1018,2224,9925,19670,34838,15878,4957,7807,2432,4758,8041,945,20228,43605,6730,50226,17756,53,7004,5653,2781,18480,110,17285,2260,538,1299,3167,16017,194,1586,1381,11611,20441,4592,2074,1158,18033,2863,2343,18835,3328,3421,4556,1810,8515,534,7531,2920,1412,1171,955,23062,1590,25725,26371,477,13008,16973,1842,33561,3388,13511,1749,20810,3922,4616,46506,1867,3924,1271,12666,1822,1230,4105,2865,18286,8126,8093,3216,18892,7831,1639,1535,1716,5416,4344,18127,2146,1396,189,553,41,19793,8197,5825,2856,7692,9828,4204,14149,2682,278,2318,20964,2388,19263,286,2389,11294,39278,574,39,4154,13263,13166,9343,2456,3640,529,1174,7687,13100,3672,51038,18915,10767,2139,19158,4328,6774,2167,12447,5362,566,4754,3328,11646,24,13986,4818,4739,585,7306,12445,5466,379,9883,839,2921,2822,1999,4312,741,1,10937,1670,4038,5989,9402,4529,8587,15206,9159,29491,4764,26749,2700,511,8521,1269,12454,3182,3503,33559,6828,22927,546,1126,810,42650,595,1264,782,8611,45,918,2077,25560,65,7967,2231,3830,12566,18616,11960,14066,10634,7046,12110,4683,2691,27931,1407,3913,12674,8990,3389,25319,459,3874,290,10885,5191,1,13676,4624,1118,7229,19029,5091,112,6057,230,10793,6054,23739,5253,11219,7635,14670,6097,1806,3638,2865,6959,82,9248,10353,2208,42,5426,1087,6522,7216,4907,794,8425,255,5742,471,1136,3590,2531,507,1686,5995,30972,348,8662,7899,1456,898,8708,22234,1065,1307,4530,167,2858,15181,1495,5689,11420,12390,286,18388,5155,50,4702,9319,1141,5716,28743,19,3407,1956,13808,2080,10706,1231,7994,3734,18244,1868,7811,52157,7979,17,7057,91,1401,45591,576,12309,2508,12047,24096,9439,707,3955,972,2435,1666,3117,18811,1636,1936,2410,10875,25,14044,2129,2154,7202,1725,160,6291,2579,303,12242,2257,67,7154,7276,50544,6359,2357,454,11148,8375,9115,777,7195,9521,1145,6843,8096,8732,30758,2845,6410,25556,2714,16050,22467,5047,3453,15826,20248,1584,16090,18339,2662,9078,1811,4303,430,12694,3323,1606,38659,696,21316,1460,37441,12725,39540,6786,4293,9954,5732,6494,6896,15742,43777,2404,15237,8964,22936,323,4944,5927,408,36280,44870,29305,17713,34730,1019,1187,4836,66,190,68,42523,7533,11702,1,9935,2050,14360,95,3136,32818,295,2331,402,2675,13106,1588,2325,797,8518,10584,20168,7267,2938,3335,2607,388,28861,1780,2661,188,217,16757,37071,12682,2258,80,463,1689,38,18085,6380,25156,844,21418,232,178,86,590,11889,1042,1955,3965,436,20983,1944,7718,43363,6000,1284,420,1655,702,780,21233,33408,297,1020,21299,14212,15492,7102,3960,6766,4920,15010,27411,373,4276,4567,12296,4172,3609,23059,31158,10620,715,3573,1998,2884,975,23382,1858,63,931,8765,3132,3189,490,1567,26648,15844,5724,1,17273,612,2489,266,11240,13879,35352,786,7570,4644,3942,3326,3975,4550,22405,3784,19560,1211,2851,24913,105,5354,1889,333,5918,22091,232,6293,7146,2014,6507,22172,153,1931,2765,92,2050,4365,1798,1969,3098,3902,17439,1388,41229,17951,1214,5511,14431,1841,7138,5104,6940,12034,454,86,46221,1748,658,128,3243,40119,392,537,15747,586,34699,2114,9035,1142,1984,212,7842,7994,9489,653,23646,7350,590,21525,76,2419,21840,794,25355,191,1,1602,1647,2449,6838,1329,27245,4874,8233,5208,8994,3293,31575,11422,7357,6179,27321,585,27415,13408,1986,29651,7018,5857,25639,4096,4875,1631,7840,1360,1216,4603,31318,4828,34007,323,596,37691,1985,7112,4215,321,44,8536,12602,106,1019,3450,3851,2871,3549,22520,698,2490,4205,25934,15213,555,2019,6071,2066,41148,7184,850,3926,4562,2442,346,6277,33775,718,10213,7369,29490,1195,4115,24761,2599,14329,6764,1621,18879,39815,33312,1045,3090,1600,32560,16682,37204,6468,10658,3901,3055,324,7536,7685,1197,9024,5528,1877,1368,248,29570,9517,12494,6816,2638,3829,6182,4721,5276,2660,2085,2389,3666,33111,17823,135,621,14168,481,7471,472,3532,4862,17362,1096,26792,1780,12583,288,39,3823,33439,28889,20675,151,147,8344,509,22,31001,49979,6998,712,32954,10589,3873,88,5851,1769,1115,417,6778,677,2991,1783,4308,6592,6582,7115,32117,4639,14025,6985,1829,184,1,3651,8540,2260,1181,4519,15075,1000,3057,2932,16673,5913,12568,50399,6000,16722,173,1518,5584,15654,8225,14432,10944,535,3934,12733,14234,26833,7126,62491,24609,12670,48816,5259,1864,24358,15,1365,1866,4928,6857,7356,4859,1046,30559,3308,24662,11782,9283,10424,353,1014,4039,6492,5473,3260,17433,11323,1393,1480,25165,11765,12275,2781,1465,29228,20206,9513,6539,8698,22740,1391,778,11524,1568,2205,7350,2662,4112,1023,4400,3840,1973,937,14300,7175,2607,11150,29170,10499,8926,191,5904,5205,2850,8427,9686,3935,3835,35093,479,368,28442,9068,3054,1179,11749,41074,8478,4573,4198,368,1111,9070,644,20476,5254,23874,6790,15,1057,5865,559,953,1748,9479,543,1338,13657,10445,19508,7317,8219,10024,2195,37206,324,10369,824,3954,8775,2767,17622,24570,1,3097,2623,8111,2311,6358,695,6740,7522,9094,2102,25824,953,18053,423,15140,237,41,19700,15408,8409,120,115,689,843,35692,23046,3517,1011,8237,2496,13391,1152,21355,5356,16787,24693,7622,2789,7212,4043,2471,12602,7949,4653,142,131,923,6400,799,7887,9397,1493,1392,2225,459,742,494,41213,13463,33528,4298,16399,56,1800,4079,12,12963,8449,297,1747,391,18949,1496,11969,2502,7473,486,7530,19010,34828,7222,13,35342,69,1996,718,2878,18940,459,4917,11905,9581,39144,14065,1075,32636,492,4996,45874,39108,260,38759,11481,9232,6791,2681,3698,3091,93,10450,7571,828,2802,2611,888,5678,1105,12324,1338,1,5873,226,4751,329,2111,15335,918,49310,43544,677,768,6505,40303,540,1324,1793,1446,1909,417,421,14916,4430,9957,6498,34693,16218,15196,439,9210,6183,13948,3623,10531,51211,194,75,15750,911,13122,17266,839,4179,21,7394,17594,11421,7122,7417,4828,13529,3544,18082,5446,21603,12062,2257,33,4253,2128,6022,476,7082,9294,27019,3245,1952,4540,4432,3644,514,5338,40207,18106,67,1345,5134,14606,959,22676,12461,15655,9575,2058,3537,8129,89,5171,854,1,22820,201,34630,9926,38798,3733,669,38681,2449,35745,54,24060,718,762,3254,12717,4434,5537,31713,1101,3278,9857,10299,17155,12748,27686,584,24450,3488,1107,662,14022,3584,6708,26906,2012,45544,5293,7,4162,25103,14680,17162,761,13489,14465,332,600,802,1379,20984,2982,31081,164,44678,4852,1143,28010,7775,9884,519,26,4942,723,844,161,94,17724,10013,23167,1181,7886,1541,4209,17914,15626,35560,921,17128,2819,4456,20510,6269,24581,2045,31063,6375,408,13234,12393,20163,2023,10644,408,15262,785,15623,3205,8351,39112,3225,422,511,10459,4052,19,26972,258,1,1,2249,168,10555,5959,3829,3529,143,50517,13813,14926,27208,291,2379,7410,187,22502,7310,20264,2730,5078,9428,151,2779,17277,1950,9517,8586,5270,852,8961,3088,375,2873,33992,6968,1537,8542,897,1141,7366,3734,32280,5,24158,12276,515,367,1635,26997,2838,12091,17682,28868,3053,28832,8837,24539,6073,1476,6688,3899,64426,15096,1594,12,8115,1815,426,9325,26251,17669,4338,15969,6787,7625,24846,8441,6850,1230,1132,28012,19142,20931,1408,25004,1325,3085,1106,2868,144,2062,50585,6332,1058,5618,5926,16233,1778,1044,4645,833,12472,79,4846,4762,1314,15748,4126,4,28064,16056,721,4146,286,4853,4853,1375,28686,7485,11543,2671,11867,27361,4942,1925,19035,230,5596,950,1701,17147,3644,874,7358,1,6149,1746,8144,48110,872,978,28732,5713,1,17127,102,9711,5075,11370,2587,2032,1089,17452,6926,16715,6061,3175,29755,2844,1255,13036,423,22387,6217,2537,1911,13242,18773,76,12246,6749,6472,28567,2136,12834,20095,13064,866,3735,1826,106,363,5407,2715,342,5702,7284,15528,6537,2396,13036,43303,4745,17184,12568,2200,29996,256,1299,1476,2302,6701,16984,4881,7267,459,1100,8867,1276,22046,19376,1726,2818,9302,762,7927,25479,10883,1205,7920,3671,586,18720,12800,20242,2918,8898,1644,6675,18350,266,16127,7509,4712,293,4893,285,648,2786,11950,3959,23551,10673,13725,12367,7733,7926,1,5889,5614,1205,919,6059,1559,21312,626,7200,1310,12225,2989,142,25049,9360,380,48366,6026,19035,155,25,43633,2066,2531,563,2767,13172,12124,4001,2555,3134,295,4350,3407,1425,5155,39122,3233,7258,496,61,344,12976,5241,3694,35909,395,3351,112,1461,3864,2156,6970,1630,4334,11249,6394,7751,645,34,10307,15401,10894,198,477,4040,2188,5389,31841,2511,7834,13917,1801,9772,3998,18693,3923,19544,5859,5408,37207,2013,710,1601,3879,3196,15161,13843,1001,5419,2017,9875,3678,13902,1602,3424,11533,6282,1571,540,4317,25989,367,539,6834,12656,400,19879,3760,1,61,273,3186,2873,5632,3957,13384,280,10888,7211,37326,20754,10968,12970,338,891,13398,1167,8167,7622,29460,21425,12052,408,29808,10276,4725,4765,12260,14321,848,2900,2047,20704,2267,9110,4084,144,29282,315,6732,23708,19704,46326,46978,19417,4424,1460,4969,821,6231,916,4158,4021,14149,13408,3,3621];
A=[343,10,35,166,1,272,62,46,227,569,145,135,347,207,65,197,50,47,31,5,429,120,131,138,279,283,454,187,74,412,28,472,126,317,260,247,457,213,289,231,9,6,110,3,308,68,5,97,4,93,438,567,93,196,15,119,4,30,117,56,92,299,316,383,306,236,227,44,397,97,281,321,489,206,65,542,294,70,137,47,154,12,468,377,216,160,111,5,278,361,32,175,419,381,53,32,137,223,43,479,415,183,109,107,32,275,80,375,162,35,373,7,248,197,22,181,8,13,109,113,112,409,214,23,17,153,59,181,203,119,471,343,307,321,494,241,389,289,493,85,26,267,337,473,356,240,61,363,28,215,74,90,370,303,325,136,237,92,307,201,218,474,65,70,210,238,46,289,30,23,5,295,37,222,187,420,83,219,86,444,57,33,526,417,419,57,4,69,665,320,284,326,37,291,25,200,159,130,350,363,223,64,81,136,38,14,490,7,354,68,366,244,162,28,131,200,150,148,40,214,11,87,164,205,21,72,20,22,64,613,54,297,271,39,89,143,119,273,309,215,5,168,1,117,314,140,130,25,358,165,21,400,202,302,16,87,483,168,293,6,153,105,264,213,344,11,254,28,108,161,150,534,300,405,346,76,13,267,303,60,122,42,16,4,47,585,495,351,49,227,199,413,227,308,300,170,630,77,105,33,118,30,17,482,145,71,217,223,82,203,8,25,22,547,505,2,191,69,123,20,183,40,23,318,375,644,11,453,151,338,61,30,690,6,72,109,9,160,422,403,234,21,136,19,457,61,455,175,68,132,94,323,317,113,278,28,185,533,589,169,64,70,219,380,279,496,2,9,173,196,387,508,377,453,656,461,131,36,286,30,271,99,76,22,396,267,518,185,65,189,18,93,204,137,399,23,16,33,405,549,484,462,17,507,14,68,8,586,577,117,128,369,361,475,165,86,93,119,141,72,373,85,161,357,143,84,142,419,506,16,145,80,37,7,375,439,388,584,66,250,390,42,367,54,212,89,29,183,82,90,398,89,6,89,7,82,12,133,19,336,183,468,50,44,452,460,43,64,156,8,137,444,8,275,20,46,530,330,93,91,162,266,1,69,303,35,225,369,589,148,12,110,155,171,197,486,252,340,194,34,500,56,235,217,22,137,36,171,28,10,260,70,309,71,63,26,33,24,34,246,196,70,77,8,2,132,443,57,431,410,251,211,130,509,221,192,67,252,230,19,502,268,74,33,25,167,499,219,278,222,152,510,59,299,312,350,159,630,141,175,20,114,43,204,28,16,62,86,348,224,2,24,36,83,384,140,122,85,257,31,36,7,228,180,527,326,253,401,87,98,276,157,118,25,247,621,52,349,72,65,224,194,34,454,54,153,60,81,316,193,221,12,211,56,13,38,217,353,190,102,146,11,65,101,93,98,140,199,35,489,20,269,54,284,364,81,105,4,91,92,587,14,155,524,392,211,145,228,103,16,448,621,445,58,619,127,73,163,183,117,125,8,241,201,578,145,27,125,51,345,133,10,3,8,229,42,27,102,680,48,184,30,90,48,1,5,153,210,197,141,151,120,27,249,240,85,173,75,321,380,57,207,101,108,593,136,52,121,229,103,216,211,163,125,61,100,5,268,15,103,317,213,372,43,63,258,134,190,667,183,228,498,125,78,100,388,20,497,7,686,35,76,172,96,593,375,43,78,80,154,41,112,5,95,33,351,52,14,130,16,154,9,244,179,267,32,515,410,129,247,50,128,57,8,69,125,48,339,94,10,253,105,43,490,1,100,198,187,151,40,40,26,7,368,252,468,251,220,76,215,115,260,309,309,76,64,229,44,58,29,8,39,265,240,102,330,318,184,84,57,347,185,364,83,234,335,404,252,466,216,259,222,241,291,67,94,70,149,20,298,18,62,413,374,250,123,288,34,204,72,10,37,309,338,143,192,186,270,62,181,101,139,37,539,442,4,388,50,130,208,129,249,275,4,52,152,373,112,182,315,18,27,61,416,91,51,57,284,76,8,376,211,112,76,72,78,477,149,334,194,40,174,45,381,207,113,51,133,432,265,140,214,204,35,445,196,36,61,507,92,237,153,241,73,26,48,76,2,262,380,210,49,78,383,20,110,278,387,55,22,339,8,252,184,118,224,640,222,215,633,191,7,12,64,19,175,163,8,473,205,310,16,4,271,89,353,227,90,464,9,292,260,1,168,389,254,312,38,29,366,132,97,3,334,25,171,357,240,183,9,30,233,122,38,191,130,2,368,370,195,442,249,37,120,24,36,88,12,296,52,193,31,304,196,55,345,47,192,92,279,28,401,35,28,42,148,413,134,226,205,9,20,28,1,150,159,103,130,550,342,485,135,93,14,98,346,138,14,279,42,215,6,268,234,112,180,213,442,95,251,16,416,251,136,38,38,107,76,204,96,84,220,35,171,263,323,156,69,384,130,202,305,116,75,270,130,382,152,272,336,396,1,4,192,37,52,214,4,286,4,574,228,58,196,94,14,27,274,6,322,120,159,80,2,395,590,29,17,476,306,566,342,75,272,201,170,391,639,78,104,83,123,134,42,24,86,417,107,32,98,425,77,289,63,27,102,558,140,253,57,268,178,51,407,222,117,28,19,26,49,548,68,532,235,263,218,31,94,52,121,15,385,337,32,471,141,18,160,186,44,69,511,96,242,142,14,26,301,131,148,44,27,363,170,179,443,311,276,77,116,2,84,126,145,131,469,148,164,164,23,8,27,21,84,174,5,510,410,18,406,7,336,2,60,24,319,422,76,528,221,555,560,167,26,154,6,179,48,462,335,142,137,270,130,82,265,16,121,13,92,612,442,3,106,307,202,92,242,141,2,23,49,114,207,344,12,273,117,40,73,152,323,146,224,326,89,180,19,285,62,139,34,480,70,151,79,20,146,374,89,258,447,23,488,78,78,31,164,57,585,36,37,657,345,39,184,419,422,106,32,165,185,102,111,224,102,352,344,57,369,3,53,9,184,13,230,525,16,63,125,40,66,12,336,126,159,335,17,247,325,9,241,146,284,88,523,297,575,171,161,181,46,123,350,24,164,62,354,108,251,289,193,71,2,489,115,553,231,124,23,41,216,151,354,27,1,83,166,99,255,389,86,313,109,36,313,525,2,466,265,52,52,127,111,134,98,45,3,12,5,18,396,579,418,2,146,17,245,450,10,32,155,135,326,252,144,8,262,373,41,38,3,442,30,207,177,408,407,8,62,193,206,2,192,181,157,134,12,12,19,337,183,172,99,192,80,295,229,60,21,192,81,294,55,104,175,230,94,202,13,113,202,56,263,617,3,343,84,294,555,415,298,322,288,547,557,6,99,63,111,125,210,40,91,93,299,4,653,346,118,348,9,623,37,80,96,275,10,269,12,543,689,19,406,131,90,199,146,474,335,367,308,266,549,17,50,255,266,57,382,33,216,193,328,115,459,359,181,165,78,282,169,47,68,73,267,315,1,344,97,29,82,226,312,326,206,23,373,125,203,217,247,72,462,40,178,20,60,45,181,70,178,188,328,115,105,89,348,269,364,1,208,347,45,10,105,144,269,334,376,44,265,197,389,1,2,150,90,356,386,368,43,353,44,115,28,425,21,237,437,685,184,304,113,45,221,5,7,256,554,372,381,490,345,2,16,3,165,149,274,4,87,18,42,395,48,142,24,85,80,10,132,463,142,202,21,290,34,31,1,292,511,105,365,11,5,50,10,458,26,25,355,98,164,64,79,465,222,637,127,146,80,40,116,141,375,187,220,617,6,605,180,266,1,75,256,491,141,112,191,356,155,73,125,43,283,224,295,412,111,18,10,106,190,108,37,23,396,43,318,103,13,89,217,41,75,185,187,390,12,67,371,27,64,98,127,231,210,36,557,155,164,7,609,26,116,202,283,66,597,431,52,32,493,56,438,131,17,333,66,6,43,130,458,207,132,3,279,449,319,18,331,146,277,70,284,26,35,177,214,222,40,419,347,36,2,134,411,201,396,67,23,44,332,78,5,79,129,38,326,322,133,64,322,63,243,346,154,311,71,88,29,108,96,77,396,93,253,454,42,41,103,108,21,454,74,37,41,351,212,34,4,238,90,108,139,441,60,529,157,75,256,1,203,272,181,242,21,122,53,375,405,80,182,220,175,134,98,208,162,123,195,26,180,382,649,17,597,231,495,16,172,81,133,263,44,255,114,223,55,60,110,2,253,2,22,109,152,6,558,85,157,173,81,598,88,185,383,6,25,289,125,93,139,303,232,91,66,49,71,43,102,118,556,18,33,180,396,36,466,92,259,124,338,10,157,51,315,414,155,95,50,20,119,204,2,335,53,31,22,232,148,178,385,16,362,263,499,58,157,173,527,98,184,256,139,169,241,481,257,116,217,22,465,19,82,569,159,380,47,91,262,19,117,184,1,9,287,30,29,1,411,130,27,501,124,40,28,6,388,376,381,24,32,142,249,39,40,17,275,144,128,114,446,248,46,34,144,427,247,50,48,62,522,639,369,292,606,149,266,305,179,143,150,264,536,206,396,429,41,116,15,47,12,281,206,10,85,6,475,314,128,529,192,10,277,589,99,58,70,98,162,324,48,218,182,301,312,26,139,211,361,23,47,134,9,236,157,11,186,59,38,69,150,64,2,211,166,210,359,105,7,79,291,157,20,320,185,72,360,43,10,474,533,183,201,58,26,231,9,135,587,307,29,325,646,253,38,372,313,70,46,509,187,37,204,608,106,345,40,1,53,324,271,47,119,166,247,104,114,11,466,254,359,5,3,200,190,27,361,339,318,21,194,30,57,68,170,85,290,453,260,194,109,86,121,85,17,404,5,87,462,368,9,21,9,100,209,401,459,22,17,14,638,99,592,236,172,376,359,42,161,339,228,174,24,56,227,368,145,183,29,90,472,38,75,206,35,469,190,335,247,149,351,54,169,211,1,331,26,288,452,276,535,20,138,70,85,118,455,135,2,417,129,134,27,100,201,122,277,250,86,5,65,18,66,27,114,119,191,20,3,149,20,30,213,45,159,559,64,392,123,44,207,15,55,217,63,121,13,233,89,21,276,376,12,159,329,30,307,59,189,384,486,187,17,448,137,19,147,35,548,269,150,236,35,157,72,84,350,59,36,29,278,421,184,78,177,40,38,275,362,108,179,233,534,8,122,72,9,67,40,132,84,214,33,245,41,25,11,426,141,12,101,203,41,75,40,25,6,537,111,227,67,565,219,110,608,8,428,168,334,3,7,49,53,70,139,224,242,406,177,6,49,22,149,630,240,246,15,20,26,326,48,277,93,65,8,47,95,268,124,37,155,10,362,505,144,62,122,46,34,353,328,286,56,215,21,27,369,62,100,140,142,132,23,67,272,8,131,102,56,127,80,19,7,53,359,190,61,468,44,84,71,95,245,33,10,373,153,259,35,70,164,4,513,335,5,75,65,628,10,107,24,410,454,55,40,518,16,453,346,335,191,352,121,408,85,523,7,327,372,10,352,97,32,271,41,375,57,75,30,82,35,559,100,264,5,97,2,8,105,86,14,85,35,34,345,54,188,132,5,147,124,69,100,13,447,4,491,28,314,156,240,550,9,71,372,116,182,517,344,367,34,233,359,116,75,23,338,142,77,110,39,292,33,123,206,52,362,209,69,429,277,74,34,538,40,94,44,175,279,399,367,47,30,74,297,456,197,84,108,18,67,428,172,82,214,565,106,39,69,167,140,100,134,249,544,40,61,226,87,67,155,21,249,263,409,289,108,79,76,62,38,19,449,13,26,293,2,304,273,165,104,102,233,3,173,544,107,211,136,1,19,24,261,110,11,224,116,357,82,1,391,71,188,19,63,67,58,50,258,118,6,125,143,79,305,420,4,74,244,405,401,191,388,281,50,376,94,187,171,1,28,125,237,199,87,81,6,153,61,221,2,150,225,60,28,80,189,546,13,34,192,26,92,10,162,441,306,283,21,5,14,23,152,283,218,680,359,118,101,91,371,179,6,33,12,57,6,21,3,55,43,125,611,34,63,110,145,44,8,22,7,1,2,67,48,262,270,324,90,171,13,110,137,11,153,124,18,142,124,5,120,361,345,115,101,179,1,85,132,574,119,256,93,22,96,490,157,91,107,9,64,18,31,183,484,209,98,74,57,34,11,382,17,201,88,48,124,513,552,62,186,134,365,165,261,123,258,229,373,1,1,40,473,220,3,192,55,41,196,28,4,92,327,83,8,11,36,416,15,13,424,229,381,413,42,20,344,99,136,141,92,49,102,250,187,274,405,189,29,64,62,185,104,369,85,366,270,18,80,230,230,271,189,1,396,164,87,162,16,553,257,167,83,16,167,69,457,307,57,142,124,24,578,77,23,47,146,7,2,297,182,348,20,212,16,53,10,343,242,221,142,532,487,308,260,206,550,45,197,89,106,333,184,441,128,266,188,374,106,13,244,38,106,75,13,171,393,378,155,138,118,82,69,215,32,149,151,22,636,223,103,63,211,127,417,466,15,221,568,218,274,155,29,167,1,62,62,95,67,23,22,71,9,29,69,152,283,406,114,104,171,280,169,42,3,480,15,17,14,202,208,384,65,46,182,175,28,36,344,33,499,163,2,102,322,109,39,320,54,267,11,13,9,42,48,63,341,14,312,105,211,198,4,20,145,160,225,1,38,203,57,292,73,27,72,149,2,143,323,158,106,418,190,35,157,322,376,446,3,9,642,109,345,28,6,163,211,102,210,28,156,37,249,222,37,340,517,50,32,29,10,157,189,14,165,203,452,62,11,1,5,47,56,229,65,59,84,83,10,366,44,22,661,6,475,137,240,160,8,160,25,177,378,172,110,204,95,223,129,99,6,161,418,232,3,23,30,15,286,24,335,58,526,196,36,14,116,93,127,494,303,264,134,237,11,115,141,237,114,44,480,3,37,12,11,116,100,54,86,197,25,27,70,59,167,362,241,323,97,42,427,287,27,178,102,6,110,452,171,158,7,157,153,77,506,289,181,300,22,267,63,115,153,72,458,151,41,262,283,446,251,147,291,214,56,156,285,6,27,6,309,10,286,181,69,417,153,326,370,111,341,134,212,237,105,206,26,171,8,462,6,285,289,22,42,61,78,119,523,186,257,161,46,24,29,135,127,16,154,97,386,492,557,17,23,264,131,299,122,148,103,598,79,316,366,1,84,28,334,81,26,142,1,3,437,233,86,3,121,1,102,182,307,400,60,100,24,74,373,193,392,220,482,36,212,21,192,41,133,12,228,1,224,348,477,18,58,164,272,4,36,222,131,112,331,210,22,231,75,239,3,1,50,5,469,107,22,22,20,136,106,148,128,47,131,397,36,89,34,239,69,124,3,144,331,141,103,178,265,41,295,283,249,26,197,430,2,242,103,33,203,13,266,13,270,18,488,224,4,73,99,91,8,129,248,6,167,424,513,72,49,336,1,103,76,190,55,267,1,97,10,104,243,146,68,290,38,426,36,593,432,384,107,64,182,127,43,565,228,135,250,57,154,474,141,58,514,232,76,60,241,139,70,215,2,53,412,8,100,154,25,36,224,263,154,110,357,4,12,294,249,57,304,64,91,17,25,105,227,370,236,303,328,83,152,225,102,287,442,111,562,235,2,220,137,42,446,3,363,90,10,51,409,194,4,128,38,153,210,72,286,73,264,147,60,232,82,129,188,27,118,10,134,126,48,24,12,236,152,294,524,49,279,228,283,373,178,185,53,429,225,50,483,68,138,18,188,44,16,129,83,523,86,128,474,286,227,80,227,25,63,111,238,38,89,15,18,3,257,356,68,152,113,299,58,347,426,31,44,349,46,204,61,409,143,418,47,3,62,141,218,379,40,125,10,15,118,317,101,639,212,132,55,332,196,170,78,143,71,18,53,40,559,2,254,58,116,92,83,208,140,61,254,51,106,60,27,186,56,1,420,53,350,272,110,104,133,547,181,329,151,480,59,15,134,142,263,33,45,384,165,249,64,42,12,607,96,66,151,121,11,33,396,265,21,90,107,432,235,462,399,227,114,129,149,176,206,288,69,89,132,127,73,346,22,58,9,456,262,1,444,72,17,247,273,252,5,467,11,228,82,290,72,155,360,183,147,46,83,102,75,30,103,116,31,11,285,18,77,101,80,112,343,6,154,16,13,51,103,93,343,153,390,62,487,91,42,36,231,241,15,17,521,13,151,190,16,114,272,198,10,240,268,3,52,174,14,491,393,54,146,42,185,153,110,17,188,153,311,20,101,572,239,2,318,12,23,505,12,171,209,146,316,257,72,201,146,72,42,213,499,22,99,37,272,98,192,47,30,141,104,13,186,89,5,232,71,111,77,514,653,69,45,21,229,163,142,160,221,112,26,156,194,182,430,35,157,346,170,266,461,52,65,343,372,217,228,367,77,92,222,76,12,263,272,60,445,14,259,29,398,207,418,373,57,236,102,125,127,182,589,127,327,158,291,13,111,329,7,381,467,400,213,447,27,17,89,4,7,2,468,302,188,1,207,30,248,2,42,513,107,40,7,60,166,595,92,12,100,392,426,107,70,51,104,37,365,31,356,14,161,195,559,358,109,2,14,419,11,339,84,255,424,323,19,44,2,7,192,30,302,71,8,470,25,92,450,127,41,8,257,42,34,546,352,55,18,502,159,308,175,42,77,79,220,570,6,48,49,353,439,58,582,324,241,16,101,237,164,11,278,21,10,19,265,77,219,459,19,511,165,153,1,205,20,67,19,115,168,373,78,467,142,129,51,95,502,304,153,225,24,104,287,20,57,42,80,63,286,7,272,248,45,515,448,13,122,126,4,58,193,281,144,168,101,192,290,542,306,231,60,321,61,147,85,83,318,10,4,499,52,120,45,360,597,43,49,200,97,604,28,92,20,63,79,134,480,233,101,412,116,11,477,2,229,336,17,330,3,1,26,171,37,257,200,457,69,490,131,180,74,519,203,266,103,291,34,286,547,33,316,76,212,312,94,179,47,251,16,46,490,330,268,374,400,31,412,238,245,197,15,5,308,141,5,17,37,87,31,230,410,157,191,161,310,185,25,129,138,128,505,90,40,55,179,30,144,66,543,42,437,79,473,29,113,352,85,227,70,67,263,524,402,19,203,91,327,493,429,448,217,83,83,60,93,90,36,174,309,20,54,29,339,183,276,550,60,482,271,84,116,105,124,134,114,379,228,4,66,517,7,224,59,41,60,252,61,275,56,259,16,4,72,354,348,476,7,4,90,101,3,564,545,386,19,609,264,400,5,456,93,82,24,370,36,66,30,56,297,76,182,327,148,302,205,25,4,1,59,131,61,113,71,242,28,71,35,603,74,245,537,65,170,6,30,126,281,123,177,175,56,677,431,254,361,233,668,393,505,569,56,156,495,25,71,27,158,164,79,192,79,456,93,287,230,380,169,20,38,78,116,243,224,212,366,24,54,581,279,324,123,25,372,292,292,101,97,267,30,32,318,30,30,381,87,79,56,83,102,32,286,147,104,64,133,550,337,215,13,99,148,245,104,361,49,86,545,7,16,303,249,67,199,175,566,112,60,105,5,17,382,13,332,70,258,424,2,25,102,216,40,246,154,8,107,442,181,330,77,119,108,121,526,25,466,28,276,106,53,245,459,1,76,82,94,37,211,35,349,110,336,94,366,65,195,6,346,9,34,250,210,177,4,3,12,64,378,301,106,16,96,46,298,19,292,193,286,264,100,46,449,162,252,271,88,105,24,8,61,131,41,638,394,121,373,87,41,43,69,512,137,535,164,462,2,164,55,158,344,218,25,106,17,319,47,131,41,105,30,191,199,443,156,8,465,5,34,11,39,197,6,178,143,171,456,236,101,446,64,132,549,433,15,541,165,103,90,49,131,65,40,150,164,63,102,200,35,134,117,378,168,1,177,31,141,41,45,175,24,510,488,16,28,84,500,16,25,91,245,38,542,25,160,75,214,134,509,182,450,58,211,514,475,126,160,564,4,7,512,11,137,198,24,127,10,113,283,294,185,178,65,356,151,410,477,230,127,49,8,84,109,619,31,197,256,272,38,80,209,59,144,9,114,514,200,174,267,142,164,74,237,243,404,412,42,49,89,10,204,35,1,237,54,527,114,389,47,44,565,27,382,9,272,66,32,62,187,137,185,515,14,60,140,123,461,208,343,70,402,445,78,22,146,202,156,465,77,669,141,13,123,461,268,333,15,140,168,5,7,74,23,476,90,449,11,518,68,243,329,114,424,31,8,102,21,80,104,3,394,295,328,24,86,69,69,588,169,464,91,213,42,322,213,379,438,321,331,228,34,374,247,327,141,359,283,161,12,196,354,288,406,89,10,7,434,109,5,389,85,1,1,116,60,264,105,42,42,13,546,401,618,391,36,94,85,17,234,196,231,681,98,119,9,76,268,126,367,130,62,13,327,38,9,33,557,300,26,97,22,28,150,46,372,2,251,156,17,11,37,413,60,162,330,359,293,412,139,465,70,67,335,364,676,332,399,110,95,23,25,307,324,297,110,192,165,291,384,208,92,29,111,450,207,323,35,415,83,37,355,37,12,25,597,92,28,179,86,247,34,32,74,19,149,8,60,113,18,175,218,3,414,451,13,322,4,76,150,134,323,106,198,245,384,596,350,43,252,5,70,66,176,248,125,52,101,1,91,202,148,501,12,12,333,257,1,183,67,273,144,451,96,73,53,411,90,178,202,70,321,76,22,135,24,306,98,32,42,307,206,5,395,84,247,326,30,196,227,218,14,55,22,267,27,79,111,38,556,269,359,103,210,207,495,55,328,389,69,368,4,45,63,51,361,258,63,392,124,24,123,97,230,578,26,159,103,16,307,352,153,17,217,41,111,359,133,467,45,296,182,234,289,79,347,256,142,10,126,46,17,45,350,44,563,146,276,276,102,235,1,168,189,104,11,169,18,344,29,293,19,402,45,11,273,379,17,607,72,390,3,2,483,99,43,20,63,137,192,355,130,56,4,70,44,35,74,435,268,95,25,2,25,159,59,323,389,52,114,11,35,165,284,88,33,54,335,77,393,572,2,116,458,150,48,6,44,70,68,375,175,202,351,169,288,103,429,233,425,87,57,570,60,191,19,240,357,260,303,33,443,23,230,64,250,20,202,229,366,21,8,77,376,12,412,134,224,115,515,65,1,4,16,143,142,125,104,237,9,166,220,391,268,112,136,8,156,219,31,129,304,390,527,183,6,382,252,50,345,239,289,54,119,215,247,126,95,50,184,410,6,84,313,251,546,497,201,413,245,92,14,91,20,117,60,343,210,76,196];
B=[486,264,105,218,34,278,87,100,354,632,300,195,491,524,283,584,396,182,94,567,628,264,309,385,682,388,577,449,104,646,78,618,671,521,359,472,524,536,493,316,143,24,246,66,566,221,14,294,36,617,455,684,343,546,189,630,84,47,580,137,264,546,409,529,651,644,287,497,693,121,594,322,523,244,230,616,391,134,232,318,242,147,488,399,393,407,286,18,407,502,140,387,499,508,115,36,185,311,259,694,524,222,657,157,265,533,93,398,168,131,436,37,684,317,74,281,39,188,287,170,339,489,497,30,53,414,547,336,211,282,518,378,422,334,683,248,429,670,512,403,28,322,659,588,371,278,93,517,94,344,106,175,526,416,500,435,651,570,395,421,464,544,126,344,557,487,73,632,601,217,13,518,64,291,374,431,630,520,563,577,227,88,561,562,442,62,308,189,686,563,416,695,44,352,181,609,376,149,527,697,315,68,130,189,396,59,694,224,619,644,371,675,282,31,314,287,257,317,41,256,46,356,468,343,56,151,26,189,260,632,59,523,536,563,662,415,214,282,389,649,52,355,4,598,316,560,426,159,648,206,45,508,580,523,78,275,603,338,446,162,202,200,657,619,605,95,672,182,248,300,162,572,433,582,372,276,41,482,436,292,245,447,486,74,689,683,557,699,694,663,207,430,260,324,326,646,685,555,196,311,196,111,33,485,303,89,258,604,409,605,19,128,285,572,534,143,671,139,130,141,230,194,75,435,510,661,23,511,213,344,90,158,691,433,651,119,631,220,560,606,343,124,294,327,566,119,502,279,455,678,356,388,517,312,290,127,474,570,676,311,591,138,278,456,496,504,70,143,278,233,604,517,401,480,680,561,175,95,513,105,502,146,209,34,534,303,637,331,486,586,462,138,594,504,442,92,335,177,620,576,510,591,248,645,345,133,474,696,597,248,217,418,675,593,640,124,351,174,219,118,687,560,452,475,218,196,238,449,689,37,146,143,297,90,621,463,536,664,680,557,500,353,673,418,401,222,34,247,299,411,566,406,342,97,132,557,105,238,608,646,485,584,114,135,694,681,73,317,243,215,195,680,114,345,52,447,591,621,251,253,289,402,15,217,460,304,268,599,672,235,308,373,453,418,483,695,264,370,428,96,585,66,315,464,242,145,91,424,469,38,586,119,572,543,85,42,61,606,102,428,197,71,115,53,21,333,542,232,496,519,575,662,329,700,574,470,104,399,260,23,601,452,145,70,31,655,592,403,409,550,442,663,581,453,594,398,531,647,290,208,188,322,238,601,39,213,124,245,484,258,15,648,146,127,578,254,190,148,562,38,403,51,326,329,559,350,673,502,140,384,413,346,553,135,386,665,297,624,129,74,308,688,181,610,191,159,574,689,392,684,638,40,452,121,145,274,691,679,476,295,647,631,123,160,594,109,408,247,46,530,87,564,126,477,451,130,597,33,136,700,588,405,165,626,506,236,420,611,605,22,532,628,542,93,683,322,320,232,557,440,542,35,337,485,677,303,426,457,191,573,267,16,94,9,264,405,550,256,698,624,474,180,384,62,87,639,586,212,505,668,636,167,272,649,635,267,312,80,585,508,59,210,132,610,674,417,191,686,258,108,549,291,336,151,237,180,8,628,45,224,486,516,473,160,628,431,383,199,678,598,600,575,208,653,609,697,263,624,627,689,153,280,351,217,640,648,64,118,161,375,652,212,35,591,251,352,363,23,189,85,445,23,567,237,501,55,559,436,196,619,288,452,697,230,342,212,546,636,619,31,517,127,518,532,2,191,339,342,249,128,443,155,19,380,328,643,565,373,361,483,661,521,478,420,526,130,418,273,188,36,152,144,502,528,151,380,508,254,147,126,375,211,531,276,295,481,411,394,522,310,375,609,490,359,146,481,114,154,67,597,250,75,616,418,310,521,612,273,281,165,414,89,421,571,478,232,499,437,289,531,630,340,679,655,536,11,635,96,355,245,173,342,374,527,544,476,376,287,635,493,103,77,65,492,425,378,118,341,664,365,428,251,268,87,91,146,484,571,442,428,531,361,274,631,598,613,308,215,700,583,673,452,279,197,471,403,52,432,541,183,330,611,244,77,123,63,229,37,370,670,610,403,237,611,196,121,325,506,59,584,365,85,262,241,340,567,652,628,245,675,629,183,27,86,245,284,482,76,595,565,686,460,652,335,324,696,697,101,465,501,463,601,195,208,490,366,700,115,85,457,384,611,10,655,41,549,387,300,561,55,124,405,468,43,356,391,139,672,508,221,603,561,193,199,554,118,124,328,501,226,539,447,442,484,77,362,273,488,311,561,62,431,647,374,159,267,466,578,502,365,212,563,237,4,287,317,412,144,635,443,677,161,388,97,162,528,191,49,656,90,614,565,284,652,195,193,437,491,205,600,109,468,421,241,59,54,132,540,279,137,471,312,633,548,445,607,225,392,527,141,203,565,557,559,337,321,592,198,446,357,504,13,39,330,151,189,663,98,361,299,681,503,410,332,626,157,274,486,235,384,319,411,207,605,418,643,296,129,675,635,656,530,362,313,267,183,553,675,335,548,514,541,177,346,79,239,594,484,220,240,428,174,319,118,83,368,593,387,254,536,432,246,395,603,409,130,315,20,40,56,648,228,538,586,578,368,571,191,286,264,273,548,354,225,514,387,22,255,233,52,671,514,231,641,528,471,43,315,432,260,374,262,655,305,251,527,420,440,102,204,7,197,694,678,510,584,348,390,512,97,17,182,78,302,205,15,621,654,226,476,117,663,25,111,58,448,471,316,638,302,694,677,305,173,615,34,454,54,691,441,382,245,428,149,328,685,143,356,17,99,689,686,12,158,317,530,457,697,173,69,28,540,261,262,603,468,663,126,696,244,230,573,470,500,491,265,584,240,460,139,279,268,521,160,333,167,437,366,634,547,696,534,481,495,151,493,92,254,64,630,551,48,686,500,189,263,452,546,199,135,248,610,667,184,252,186,441,565,148,468,74,402,181,339,73,456,609,17,596,306,69,525,559,674,274,273,526,597,262,453,43,659,436,687,186,572,557,576,245,445,257,417,448,443,584,523,240,488,333,677,344,294,80,137,527,230,664,258,461,66,589,312,346,363,569,453,99,499,654,363,591,344,599,457,238,369,613,16,555,472,110,163,676,288,181,157,119,10,86,156,44,680,640,438,5,575,135,289,688,21,510,222,431,621,289,368,30,378,680,283,104,210,528,39,231,434,497,507,546,313,460,400,20,544,322,684,455,128,32,205,515,185,428,306,660,152,385,543,567,163,308,396,491,368,185,337,529,98,455,431,117,697,78,369,622,294,508,85,366,695,595,378,584,449,578,610,220,271,219,189,697,286,208,102,193,598,91,654,641,618,368,595,627,75,548,552,485,299,574,489,555,693,138,452,624,187,206,154,662,503,435,659,361,610,319,77,676,403,266,632,460,409,526,432,487,633,367,226,374,89,371,387,71,80,313,564,437,5,678,385,241,122,237,659,363,425,35,395,213,289,682,431,89,553,73,542,572,205,51,481,105,200,506,444,270,373,229,547,586,413,117,464,636,171,323,162,146,320,516,413,128,344,335,640,200,326,488,303,432,598,509,294,498,352,137,82,476,38,352,553,692,350,463,364,102,684,157,67,497,638,569,445,571,484,15,48,330,477,165,579,88,227,233,48,550,642,156,115,156,442,273,331,482,518,572,24,338,121,200,25,686,600,161,435,581,22,480,197,594,48,229,380,509,176,184,137,645,386,677,463,352,86,424,195,165,426,328,266,639,166,624,189,472,649,657,448,554,343,421,297,424,648,249,685,76,507,521,449,692,214,62,31,513,390,199,90,190,672,160,453,177,37,169,237,93,398,233,677,583,39,608,407,32,231,259,246,493,219,640,683,223,178,172,694,72,239,246,382,679,662,475,55,80,500,88,694,452,131,467,440,497,165,411,577,450,249,5,502,466,340,183,481,285,495,71,692,51,60,421,258,491,56,493,693,258,513,570,419,419,467,312,132,254,575,588,25,90,485,76,355,535,177,187,348,84,605,434,372,351,310,274,43,542,192,447,684,185,397,508,538,140,319,330,126,514,76,328,80,625,468,156,60,260,180,122,464,552,62,679,273,242,402,456,255,439,251,483,496,439,87,381,693,518,249,379,393,136,124,353,193,681,210,663,213,678,679,41,618,366,526,154,244,547,318,299,271,405,202,343,142,141,448,3,430,26,226,571,490,31,582,112,298,499,95,635,285,186,524,51,89,312,238,661,251,511,595,415,115,169,500,258,137,626,620,175,42,629,640,82,647,283,424,566,385,146,574,291,664,580,425,235,65,163,342,634,17,373,199,239,47,396,373,557,615,112,542,483,695,355,444,598,595,111,494,672,662,304,507,517,441,191,267,356,588,383,363,595,273,611,333,466,510,238,492,221,23,547,431,698,254,10,531,296,207,640,253,77,50,36,399,565,578,180,272,183,397,83,100,84,467,257,404,234,464,617,293,610,363,437,338,143,62,230,644,640,544,540,695,224,651,543,180,273,433,483,682,215,432,617,136,146,31,56,81,445,261,126,412,580,636,507,530,683,324,12,529,600,331,143,551,408,571,391,64,281,687,377,396,167,216,363,543,67,125,524,300,252,211,276,451,588,74,491,360,113,67,306,432,293,637,174,57,137,460,168,553,689,336,320,451,82,183,692,612,359,593,112,31,381,115,186,696,651,34,364,669,441,657,537,365,590,121,645,200,67,458,614,278,364,349,2,163,505,501,116,122,235,695,291,119,341,589,504,504,615,256,389,204,32,552,527,445,142,396,39,635,442,537,95,391,616,359,326,596,88,131,286,28,506,7,351,641,669,16,573,24,305,506,469,687,88,23,43,698,566,618,374,349,400,431,110,462,664,475,235,259,95,379,381,460,555,278,340,637,150,655,491,71,523,204,371,349,208,461,315,312,564,15,408,160,398,500,324,683,142,392,175,193,672,608,520,32,530,276,217,118,151,292,202,633,319,341,230,76,23,548,89,227,192,329,136,239,687,95,139,253,103,290,699,76,510,536,181,280,30,614,663,118,378,454,240,624,109,429,456,42,490,517,203,405,594,385,496,649,240,45,539,439,45,466,101,555,492,225,587,80,226,308,170,424,167,218,165,451,436,541,131,222,69,542,462,658,255,317,250,660,631,123,357,31,333,199,142,187,574,124,329,148,36,63,538,220,46,345,315,44,295,617,30,17,697,541,337,197,700,609,522,654,65,470,437,417,80,8,96,135,162,593,239,243,700,189,10,68,87,683,683,542,482,134,330,65,645,174,364,577,95,516,268,114,459,162,679,339,163,444,556,438,102,184,72,109,565,645,474,532,345,102,253,529,111,113,250,292,681,36,80,514,132,225,116,128,338,600,33,602,242,436,471,372,620,148,221,145,248,488,223,140,629,381,674,102,411,545,6,591,658,93,264,79,661,107,554,178,509,541,493,515,620,120,629,426,479,367,439,285,696,453,694,681,543,686,83,373,450,162,308,90,380,332,81,44,211,614,611,448,282,414,178,3,185,191,345,515,116,70,91,501,226,371,174,159,160,659,327,179,76,528,392,521,315,443,538,518,683,177,318,606,137,483,688,427,417,130,410,372,372,109,34,616,275,233,112,80,357,117,173,288,57,494,314,73,501,403,547,116,562,100,247,585,232,461,640,585,96,43,247,365,525,544,412,247,28,193,699,555,454,547,659,121,157,455,681,241,305,148,570,630,72,160,343,596,109,570,56,542,355,600,619,109,130,404,640,562,158,640,17,280,309,139,523,542,270,287,128,265,55,524,667,593,314,333,4,193,46,359,401,52,552,263,670,149,4,681,83,408,207,180,118,183,283,590,216,501,172,440,551,504,494,335,662,574,418,483,272,596,419,499,582,376,447,184,3,117,165,444,604,423,140,139,154,69,333,8,258,340,238,52,148,192,556,64,326,473,287,419,230,349,597,627,314,602,543,36,462,504,427,222,696,396,205,368,117,506,651,90,38,343,123,103,98,9,122,138,128,671,435,198,340,189,54,34,133,9,26,12,77,643,361,566,640,148,244,15,430,407,549,261,183,118,607,188,14,700,645,349,118,241,202,278,129,174,642,175,599,162,64,202,616,189,134,122,46,489,19,171,329,640,424,253,93,651,277,29,481,104,322,309,64,139,611,686,127,207,374,437,603,338,350,313,428,677,112,97,286,544,283,71,463,432,436,641,287,375,342,583,695,13,85,45,446,629,118,496,695,466,538,290,136,616,127,165,238,284,315,157,287,542,403,641,321,53,150,81,205,442,408,700,415,421,401,575,336,378,512,264,101,627,191,188,452,83,667,428,435,291,438,541,109,676,567,82,368,216,40,669,147,79,50,699,26,55,299,366,398,87,637,33,103,15,632,513,581,451,612,565,684,442,680,653,90,419,254,228,589,677,486,592,681,281,432,116,66,560,278,487,381,247,301,693,571,160,157,159,194,180,298,395,184,222,35,640,250,624,233,238,467,441,634,19,409,610,479,657,310,80,396,93,332,219,302,114,81,84,300,184,533,626,415,679,678,160,636,200,579,328,115,42,508,24,60,39,358,280,410,410,331,263,288,215,406,368,43,660,320,28,171,673,151,145,410,433,697,60,75,102,63,94,119,390,150,553,111,520,522,39,248,148,169,310,6,328,624,98,381,629,100,151,327,12,527,403,161,141,581,495,123,540,553,591,565,36,570,648,620,425,479,29,323,231,428,337,52,158,591,261,481,122,390,539,59,37,141,641,563,192,246,228,263,545,75,74,580,18,186,107,279,128,656,276,145,570,669,130,124,685,310,496,402,355,201,334,267,274,435,450,252,172,233,573,231,395,422,42,315,491,632,58,370,193,269,310,92,371,548,619,435,187,130,138,413,666,596,349,464,525,621,85,690,428,320,120,420,614,354,394,352,62,390,112,113,174,320,101,221,242,515,384,655,491,459,147,170,597,444,46,219,165,83,120,544,621,315,72,435,265,377,537,347,188,343,85,333,315,135,305,238,597,555,198,282,299,577,288,193,521,370,298,284,289,55,271,138,625,286,376,273,177,564,502,356,528,186,686,592,264,476,133,333,622,480,24,467,56,610,351,96,268,602,360,451,657,499,327,318,94,595,31,484,128,29,688,178,466,568,633,22,30,437,651,409,427,568,268,644,346,342,389,12,191,523,494,228,27,302,5,10,659,580,107,646,343,137,581,332,325,465,401,559,185,135,476,218,405,266,524,60,685,654,596,45,359,265,372,42,528,615,535,417,94,566,442,246,505,246,294,363,690,614,227,658,264,461,615,15,404,9,565,209,111,226,95,161,252,322,285,81,172,413,618,178,207,533,571,314,637,152,646,355,425,206,647,249,555,400,581,59,202,562,90,257,536,637,215,306,289,84,333,530,555,305,7,133,134,189,270,577,323,23,663,568,683,424,88,636,2,182,451,290,309,288,8,129,26,136,472,245,265,365,163,627,287,600,492,533,169,458,242,162,205,582,613,501,290,242,229,493,151,77,558,478,331,248,452,265,84,270,12,104,471,470,574,180,448,61,280,301,184,153,419,10,132,658,277,197,404,160,195,68,165,262,312,592,290,485,689,317,546,533,628,623,473,118,563,697,9,347,606,183,479,24,666,686,520,70,502,545,11,366,197,224,292,552,495,108,479,479,208,524,601,286,218,578,337,20,205,312,494,125,193,313,224,356,537,260,361,394,340,694,187,275,120,686,313,180,491,333,371,699,672,491,454,186,427,655,236,445,655,665,392,108,651,85,65,366,645,655,317,204,33,69,475,451,467,234,174,393,327,641,503,426,47,439,83,484,436,576,669,549,177,33,67,409,302,626,44,391,28,17,328,427,541,671,354,255,570,608,409,615,132,351,254,609,215,42,647,64,431,547,226,392,476,523,160,606,301,86,142,65,409,434,61,4,690,201,418,444,581,477,225,640,494,476,165,564,90,68,193,359,684,180,168,620,502,541,519,66,64,641,432,692,238,452,476,441,517,484,190,322,583,550,382,589,448,423,360,285,204,186,697,432,170,446,451,619,82,578,578,95,51,552,463,24,488,403,25,298,361,312,30,676,527,572,91,641,445,642,538,406,266,55,94,385,290,372,258,529,39,18,350,107,175,184,426,251,364,381,196,22,410,82,683,268,628,390,653,191,535,107,172,37,380,271,16,344,608,277,227,360,156,635,431,345,454,596,388,48,77,297,48,623,530,189,179,413,528,654,215,54,481,346,665,248,570,661,363,619,434,304,287,637,24,522,477,520,365,597,176,207,279,532,122,239,578,456,434,43,417,446,197,65,183,326,680,359,424,106,356,289,83,594,235,674,677,91,211,117,394,647,590,256,306,490,48,307,478,266,609,37,645,497,606,465,660,87,338,418,624,496,312,526,108,373,670,619,19,556,404,368,499,56,280,368,487,385,536,650,104,286,140,427,457,497,695,212,365,210,298,19,301,369,57,417,523,488,345,646,55,209,389,7,57,13,475,611,252,2,671,35,424,5,547,515,317,287,646,161,168,657,219,31,306,684,540,661,97,355,247,125,549,96,497,225,247,459,599,547,281,303,614,605,54,673,510,478,472,324,35,230,4,282,249,98,311,288,290,645,466,359,640,589,497,25,451,559,96,573,452,71,221,590,472,316,403,506,407,225,328,619,145,119,173,637,491,423,588,591,256,479,170,429,538,99,327,53,89,66,563,432,453,465,36,581,311,413,4,648,67,322,103,625,561,484,192,544,268,627,202,150,555,331,583,307,36,403,395,28,207,63,444,417,535,15,540,519,493,637,669,47,321,199,437,529,609,362,187,309,686,261,346,699,391,263,596,610,148,158,464,282,658,207,26,544,687,165,46,504,627,57,138,408,130,620,70,135,26,121,525,210,564,295,190,598,559,12,509,12,359,536,97,374,88,3,225,237,325,448,377,572,290,623,158,317,498,559,525,339,179,413,502,387,668,49,516,322,409,361,320,683,204,399,471,79,511,514,593,502,513,432,445,361,405,602,37,273,435,192,54,68,375,632,219,399,683,554,222,427,455,211,308,249,273,150,557,310,118,647,241,44,221,94,580,88,438,345,579,283,270,433,484,319,105,217,302,583,691,174,626,566,527,679,574,556,475,558,597,373,504,636,364,196,583,149,140,431,510,434,624,697,471,578,302,471,447,327,261,251,457,447,665,19,98,602,54,380,210,47,204,254,440,342,59,305,59,199,104,514,417,619,57,12,312,227,41,602,615,393,474,699,415,688,235,645,322,99,535,700,104,73,69,666,533,245,677,388,542,428,502,44,324,8,236,255,330,416,137,587,159,80,247,674,605,260,621,112,380,22,386,516,626,618,518,368,320,678,496,430,601,459,695,555,620,580,618,279,516,87,176,252,230,338,487,449,98,623,141,332,602,417,360,456,75,347,480,317,630,230,505,36,442,630,335,468,190,90,499,390,297,119,310,544,232,223,545,158,282,649,129,159,319,84,387,154,581,200,301,428,273,593,462,581,428,560,232,442,355,426,51,245,579,10,19,394,252,124,281,373,607,342,673,148,627,105,545,118,472,78,282,674,36,65,204,240,217,615,319,559,524,609,575,493,242,441,230,582,683,463,647,522,426,651,362,510,683,2,254,92,99,69,682,589,435,230,631,422,429,512,567,626,637,21,65,495,624,295,251,484,67,138,424,421,180,595,425,494,357,129,315,563,345,634,143,123,498,311,284,423,302,309,481,38,131,358,289,696,398,215,552,376,45,442,143,692,177,659,323,634,5,306,83,677,534,271,48,133,30,465,543,152,385,140,496,474,209,450,388,503,662,38,214,358,54,245,19,365,274,198,670,644,423,563,123,420,655,460,473,551,174,212,98,159,589,70,354,340,270,435,121,278,375,384,258,633,357,12,366,35,375,143,116,527,96,672,608,458,63,647,507,52,345,243,308,220,594,53,469,517,257,700,597,301,657,448,369,532,578,266,189,582,264,11,592,12,472,604,85,139,40,124,581,497,343,232,336,630,564,564,600,313,237,435,627,429,159,681,650,446,510,606,54,252,559,420,627,29,544,562,284,313,381,256,299,491,324,623,634,440,390,207,122,313,250,668,12,273,137,532,549,428,147,291,683,50,483,213,517,116,482,154,288,233,466,563,31,532,207,197,469,343,423,177,656,468,109,66,595,482,314,469,216,690,185,46,220,507,328,528,18,418,328,46,119,545,39,548,536,560,13,685,153,286,427,310,650,420,86,699,67,352,118,402,498,495,630,405,277,77,371,596,297,603,324,291,161,337,464,508,489,597,504,698,479,441,533,443,610,510,459,619,17,249,525,344,433,124,87,71,621,625,9,526,282,2,133,603,237,357,179,154,53,418,561,655,674,405,137,155,141,675,414,274,436,690,653,429,651,262,594,152,615,374,89,119,544,178,21,37,625,425,203,546,87,578,474,185,501,7,334,398,147,14,87,631,176,370,406,614,544,420,470,636,672,512,552,411,700,585,480,452,363,67,62,448,390,365,123,643,168,407,610,593,379,177,247,461,341,575,412,691,429,142,667,353,501,34,683,302,181,364,107,394,84,48,120,26,500,206,436,544,21,203,307,19,459,498,67,633,17,529,513,536,700,616,202,515,396,638,384,554,614,128,115,77,589,508,435,266,159,2,468,315,154,602,129,17,385,465,2,404,431,580,403,517,503,215,267,581,370,202,410,122,626,187,111,319,333,373,287,167,406,431,494,30,661,224,429,621,48,586,265,567,25,432,163,498,135,353,274,154,661,432,370,169,487,491,549,336,478,611,262,690,48,607,330,88,456,477,188,399,579,343,218,286,607,664,38,427,524,19,524,643,162,466,625,108,240,430,266,502,266,371,307,683,427,253,433,290,342,24,472,163,86,46,582,78,639,424,528,393,421,653,4,521,427,598,147,433,45,633,657,455,31,498,304,23,600,478,48,628,260,586,199,133,554,178,180,182,82,291,456,698,182,562,115,225,85,61,261,495,384,646,151,70,146,550,326,394,646,358,274,121,55,175,369,391,435,92,414,150,520,647,53,179,603,193,599,19,451,232,553,401,590,540,376,289,492,555,593,384,625,91,103,617,338,215,395,694,397,266,401,150,575,290,403,226,411,113,416,536,384,195,21,111,619,41,653,444,250,391,624,101,3,22,49,235,259,335,170,304,247,528,427,440,321,230,589,136,646,668,48,501,504,598,581,243,124,456,440,371,349,658,524,203,325,287,464,141,500,63,276,555,44,352,676,302,558,563,615,589,585,248,576,231,29,238,432,452,307,519,259];